1. Field of the Invention
This invention relates to a structure and a method of implementing custom logic functions in an integrated circuit logic device and more specifically to the reallocation of product terms after pins of the device have been committed.
2. Description of the Prior Art
In response to the increasing need for flexibility and speed in integrated circuit (IC) design, a class of IC's known as programmable logic devices (PLDs) was developed. PLDs enable the designer to custom program arbitrary logical functions in an IC chip, according relative ease and flexibility in testing prototypes and making design changes.
FIG. 1 illustrates one PLD architecture which includes an array of function blocks 1, 2, 3, 4 interconnected via an interconnect matrix (UIM) 5. For simplicity, only one function block is shown in detail. The input lines 6 into function block 1 are programmably combined into a number of AND gates 7 in an AND array 8. The output lines 9 from AND array 8 are called product terms (or bit lines). Product terms 9 of AND gates 7 are provided to one of a series of macrocells (MCs) 10 in each logic block.
The architecture of a typical macrocell 10 is shown in FIG. 2. Macrocell 10 configures the outputs of AND array 8 of FIG. 1 and may perform additional logic on the output signals of AND array 8. Macrocell 10 contains an OR gate 11 into which product terms are gated, and a register (flip flop) 12 for storing the output signal of OR gate 11. The signals on output line 13 of OR gate 11 and output lines 13a and 13b of register 12 are programmably routed by setting the multiplexers (MUXs) 14, 15 and 16 with configuration bits on their control terminals, each specifying the output state of the respective MUX.
Macrocell 10 advantageously provides a relatively large number (eight) of product terms 11.1 per macrocell. However, a fixed product term count is not flexible enough to handle the product term count variability that arises. Specifically, user product term requirements for a logic function typically vary widely, anywhere from one to sixteen product terms or more, depending on the complexity of the logic function. In fact, single product term functions are quite common. For logic functions requiring less than eight product terms in macrocell 10, the unused product terms are wasted. For functions requiring more than eight product terms, the function must be split up into two or more subfunctions, each of which can be implemented with the available eight product terms of a macrocell. The results of the subfunction operations must make additional passes through the AND array to be recombined in other macrocells, thus incurring a significant time delay in the execution of complex logic functions.
To address the need for a flexible macrocell architecture, more recent PLDs feature macrocells with the ability to direct their OR gate output signals into adjacent macrocell OR gates, a feature known as cascading. Cascading enables product terms associated with more than one macrocell to be logically combined in a single macrocell. This process is known as product term expansion.
Product term expansion is particularly useful during the design of complex integrated circuitry. A serious problem introduced by PLD architectures is that, after device output pin locations are committed (as on a printed circuit board), further alterations of the application logic implemented within the PLD often cannot be accomplished without relocating some of the output pins. The problem of relocation is more prevalent when logic functions have already been formed using product term cascading. Relocation of the output pins results in design delay and expense.
Certain prior art devices provide for the reallocation of product terms by allowing a first cluster of macrocell product terms (e.g., 3 or 4) to be shifted to a first neighboring macrocell and allowing a second cluster of macrocell product terms to be shifted to a second neighboring macrocell. Either all or none of the product terms in the cluster are reallocated. Moreover, each cluster cannot be reallocated beyond its associated neighboring macrocell.
Other prior art devices provide for the reallocation of product terms by providing a path between a series of macrocells. Fixed blocks of four product terms are propagated in a predetermined direction along this path to any one of the macrocells. Yet other devices incorporate macrocells which allow product term expansion without additional passes through macrocell logic. Such macrocells work by "stealing" all the product terms of one or both of its neighboring macrocells, for a total of up to 16 product terms. These macrocells can only "steal" product terms from its immediate neighbors, thereby limiting the flexibility of the macrocells. Moreover, these macrocells are also limited to 16 product terms, and the register within a macrocell whose product terms are stolen is thereby rendered useless.
FIG. 3 shows a macrocell 17 disclosed in Pedersen U.S. Pat. No. 5,121,006. In macrocell 17, cascading is accomplished by setting the configuration bit of MUX 18 to logic 1, thereby directing the signal on output line 19 of OR gate 20 into OR gate 21 of an adjacent macrocell 22. By cascading a series of macrocells in this way, a selectable number of product terms are gated together. For example, OR gate 33 from adjacent macrocell 34 is shown cascaded into OR gate 20 of macrocell 17. The cascading described in Pedersen is uni-directional.
If not all of the product terms in macrocell 17 are provided to adjacent macrocell 22, the unused product terms can be routed to the input of exclusive OR gate 36 or to the secondary inputs of register 32. This routing is perforated by means of switches 23, 24, 25, 26, 27 and the MUXs 28, 29, 30, 31. The circuit of Pedersen undesirably increases complexity and thus compromises speed. Additionally, macrocell 17 does not provide means for performing an OR operation on the unused product terms.
Other patents which discuss the reallocation of product terms include: U.S. Pat. Nos. 4,758,746 (Birkner et al.); 4,912,345 (Steele et al.); 4,933,577 (Wong et al.); 5,027,011 (Steele); 5,027,315 (Agrawal et al.); 5,136,188 (Ha et al.); 5,260,611 (Cliff et al.) and 5,309,046 (Steele).
Therefore, a need arises for a high speed product term allocation structure that supports the flexible reallocation of product terms among macrocells, even after the device pins have been committed. In particular, a need arises for a product term allocation structure which allows (1) routing of product terms in a bi-directional manner between macrocells, (2) routing of product terms through a plurality of macrocells, (3) routing a variable, selectable number of product terms without a loss of capacity in the macrocell from which the product term is routed, and (4) importing product terms to perform a large function within a local macrocell, while simultaneously exporting product terms from the local macrocell to another macrocell, to maintain the committed pinout during the design phase. None of the above-mentioned documents, nor any combination of the above-mentioned documents, disclose a device which provides these desired advantages.